/**
 * 链表-链表相交-力扣0207
 */
public class Practice_20 {
    public static void main(String[] args) {
        ListNode headA = new ListNode(4);
        ListNode node2 = new ListNode(1);
        headA.next = node2;
        ListNode node3 = new ListNode(8);
        node2.next = node3;
        ListNode node4 = new ListNode(4);
        node3.next = node4;
        ListNode node5 = new ListNode(5);
        node4.next = node5;


        ListNode headB = new ListNode(5);
        ListNode n2 = new ListNode(0);
        headB.next = n2;
        ListNode n3 = new ListNode(1);
        n2.next = n3;

        n3.next = node3;

        ListNode t = getIntersectionNode(headA, headB);

    }

    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {

        if (headA == null || headB == null) {
            return null;
        }

        int lenA = 0;
        ListNode tmpA = headA;
        ListNode tmpB = headB;
        while (tmpA != null) {//获取长度
            lenA++;
            tmpA = tmpA.next;

        }

        int lenB = 0;
        while (tmpB != null) {//获取长度
            lenB++;
            tmpB = tmpB.next;

        }


        ListNode curB = headB;
        ListNode curA = headA;
        if (lenB > lenA) {//谁的长度长，往后移动节点到相同长度的位置（从后往前数节点数相同）
            for (int i = 0; i < lenB - lenA; i++) {
                curB = curB.next;
            }

        } else {//谁的长度长，往后移动节点到相同长度的位置（从后往前数节点数相同）
            for (int i = 0; i < lenA - lenB; i++) {
                curA = curA.next;
            }
        }
        while (curA != null) {//长度相同后，再同时向后移动，获取相同指针的节点
            if (curA == curB) {
                return curA;
            }
            curA = curA.next;
            curB = curB.next;
        }
        return null;
    }
}
